//1.顺序合并,k个链表,每个链表n个节点，第一次合并到最后一次合并的次数2n,3n,...到kn，时间复杂度累加是O(kn^2)
class Solution {
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr) return list2;
        if(list2 == nullptr) return list1;
        ListNode* judge = list1->val > list2->val ? list2: list1;
        ListNode* ret = judge; //返回新链表
        while(list1 || list2) {
            if(judge == list1) 
                list1=list1->next;     
            else 
                list2=list2->next;

            if(list1==nullptr || list2==nullptr)
                break;    

            judge->next = list1->val > list2->val ? list2: list1;
            judge=judge->next;
        }
        if(list1 == nullptr)
            judge->next = list2;
        if(list2 == nullptr)
           judge->next = list1;

        return ret;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int _size = lists.size();
        if(_size == 0)
            return {};
        if(_size==1) 
            return lists[0];
        
        ListNode* temp = mergeTwoLists(lists[0], lists[1]);
        for(int i = 2; i < _size; ++i) {
            temp = mergeTwoLists(temp, lists[i]);
        }
        return temp;
    }
};

//2.分治合并,在方法一的基础上修改。递归会使用到 O(logk) 空间代价的栈空间，每次是kn次操作,时间复杂度O(kn * logk),空间复杂度也有变化 O(logk) 
class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

//3.优先级队列 -----渐进空间复杂度为 O(k)
class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q; //以Status的方式定义小堆

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};


